package com.algorithm.贪心;

import java.util.Arrays;

/**
 * 假设有 25 分、20 分、5 分、1 分的硬币，现要找给客户 xxx 分的零钱，如何办到硬币个数最少?
 */
public class 零钱兑换 {
    public static void main(String[] args) {
        Integer[] faces = {25, 5, 10, 1};
        int money = 8972;
        coinChange1();
        coinChange2(faces, money);
    }

    /**
     *
     * @param faces: 假设有 25 分、20 分、5 分、1 分的硬币，数组
     * @param money: 找给客户的钱
     */
    static void coinChange2(Integer[] faces, int money){
    Arrays.sort(faces, (Integer f1, Integer f2) -> f2 - f1);
    int coins = 0, i = 0;
    while (i < faces.length) {
        if (money < faces[i]){
            i++;
            continue;
        }
        System.out.println(faces[i]);
        money -= faces[i];
        coins++;
    }
    System.out.println(coins);
}

    static void coinChange1() {
        int[] faces = {25, 5, 10, 1};
        Arrays.sort(faces);
        int money = 8972, coins = 0;

        for (int i = faces.length - 1; i >= 0; i--) {
            if (money < faces[i]) {
                continue;
            }
            System.out.println(faces[i]);
            money -= faces[i];
            coins++;
            i = faces.length;
        }
        System.out.println(coins);
    }
}
